package top.minuy.structure.tree.heap;

import top.minuy.structure.linear.array.Array;

/**
 * 最小堆
 *
 * @author Minuy
 * @time 13:29
 * @date 2021/9/13
 * @param <E> 支持可比较泛型
 */
public class MinHeap<E extends Comparable<E>> {
    /**
     * 存堆数据的数组
     */
    private Array<E> array;

    /**
     * 新建一个最大堆，指定堆容量
     *
     * @param capacity 堆容量大小
     */
    public MinHeap(int capacity) {
        array = new Array<>(capacity);
    }

    /**
     * 新建一个堆
     */
    public MinHeap() {
        array = new Array<>();
    }

    /**
     * 新建一个最大堆，并且传入一个数组
     *
     * @param arr 传入的数组
     */
    public MinHeap(E[] arr) {
        array = new Array<>(arr);
        heapify(array);
    }

    /**
     * 获取堆的大小
     *
     * @return 堆大小
     */
    public int getSize() {
        return array.getSize();
    }

    /**
     * 查看堆是否为空
     *
     * @return 堆是否为空
     */
    public boolean isEmpty() {
        return array.isEmpty();
    }

    /**
     * 获取左孩子的索引
     *
     * @param index 父节点索引
     * @return 左孩子索引
     */
    private int getLeftChildIndex(int index) {
        return index * 2 + 1;
    }

    /**
     * 获取右孩子的索引
     *
     * @param index 父节点索引
     * @return 右孩子索引
     */
    private int getRightChildIndex(int index) {
        return index * 2 + 2;
    }

    /**
     * 获取父节点索引
     *
     * @param index 子节点索引
     * @return 父节点索引
     */
    private int getParent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("The root node doesn't have parent.");
        }
        return (index - 1) / 2;
    }

    public void add(E e) {
        array.addLast(e);
        siftUp(array.getSize() - 1);
    }

    /**
     * 上浮函数，把符合条件的当前节点上浮到合适位置
     *
     * @param index 当前节点
     */
    private void siftUp(int index) {
        /*
        // 这么写虽然简洁，但是不直观
        while(index !=0 && array.get(getParent(index)).compareTo(array.get(index))<0){
            array.swap(getParent(index), index);
            index = getParent(index);
        }
        */
        int myselfIndex = index;
        int parentIndex;
        while (true) {
            if (myselfIndex == 0) {
                // 根节点，不需要处理了
                return;
            }
            parentIndex = getParent(myselfIndex);
            // if (array.get(parentIndex).compareTo(array.get(myselfIndex)) >= 0) {
            if (array.get(parentIndex).compareTo(array.get(myselfIndex)) < 0) {
                //如果父节点大于等于当前节点，不需要上浮了
                return;
            }
            array.swap(parentIndex, myselfIndex);
            myselfIndex = parentIndex;
        }
    }

    public E findMin() {
        if (getSize() == 0) {
            throw new IllegalArgumentException("FindMax failed. Array is Empty.");
        }
        return array.get(0);
    }

    /**
     * 取出堆中的最大元素
     *
     * @return 最大元素
     */
    public E extractMin() {
        // 拿出最大元素
        E ret = findMin();
        // 最小元素与末尾元素交换位置
        array.swap(0, getSize() - 1);
        // 删掉处于末尾的最小元素
        array.removeLast();
        // 下沉元素
        siftDown(0);
        return ret;
    }

    /**
     * 把无规律数组整理成最大堆
     */
    private void heapify(Array<E> arr) {
        for (int i = getParent(arr.getSize() - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    /**
     * 取出堆中的最大元素，然后再添加一个元素
     *
     * @param e 添加的元素
     * @return 取出的最大元素
     */
    public E replace(E e) {
        E ret = findMin();
        array.set(0, e);
        siftDown1(0);
        return ret;
    }


    private void siftDown1(int index) {
        int leftChildIndex, rightChildIndex;
        E leftChild, rightChild, target;
        while (index < getSize()) {
            leftChildIndex = getLeftChildIndex(index);
            rightChildIndex = getRightChildIndex(index);
            target = array.get(index);

            if (leftChildIndex < getSize() && rightChildIndex < getSize()) {// 左右孩子都存在
                leftChild = array.get(leftChildIndex);
                rightChild = array.get(rightChildIndex);

                if (leftChild.compareTo(rightChild) < 0) { // 左孩子大
                    if (leftChild.compareTo(target) < 0) { // 大于当前节点
                        array.swap(leftChildIndex, index);
                        index = leftChildIndex;
                    } else { // 子节点都小于当前节点了
                        return;
                    }
                } else { // 右孩子大
                    if (rightChild.compareTo(target) < 0) {// 右孩子大于当前节点
                        array.swap(rightChildIndex, index);
                        index = rightChildIndex;
                    } else { // 子节点都小于当前节点了
                        return;
                    }
                }
            } else if (leftChildIndex < getSize() && rightChildIndex >= getSize()) {// 只有左孩子
                leftChild = array.get(leftChildIndex);
                if (leftChild.compareTo(target) < 0) { // 左孩子比目标节点大
                    array.swap(leftChildIndex, index);
                    // index = leftChildIndex;
                    // return;
                }
                //                else {
                //                    return;
                //                }
                return;
            } else { // 左右孩子都没有，不需要处理了
                return;
            }
            // 处理完可以直接退出了，这种情况只有在最后面才发生
        }
    }


    private void siftDown(int index) {
        int rightChildIndex, minChildIndex;
        while ((minChildIndex = getLeftChildIndex(index)) < getSize()) {
            rightChildIndex = getRightChildIndex(index);

            if (rightChildIndex < getSize() && array.get(rightChildIndex).compareTo(array.get(minChildIndex)) < 0) {
                minChildIndex = rightChildIndex;
            }

            // if (array.get(maxChildIndex).compareTo(array.get(index)) <= 0) {
            if (array.get(minChildIndex).compareTo(array.get(index)) > 0) {
                return;
            }

            array.swap(minChildIndex, index);
            index = minChildIndex;
        }
    }

}
